from typing import List


class Solution:
    #* 贪心：排序+二分查找
    #* Time: O(n^2log(n))
    def triangleNumber(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 2: return 0

        res = 0
        nums.sort()
        for i in range(n):
            if nums[i] == 0: continue
            for j in range(i+1, n):
                if nums[j] == 0: continue
                l, r, k = j+1, n-1, j
                while l<=r:
                    mid = (l+r) // 2
                    if nums[mid] < nums[i]+nums[j]:
                        k = mid
                        l = mid + 1
                    else:
                        r = mid - 1
                res += k-j

        return res
